#pragma once
#include <iostream>
#include <vector>

template <class T>
class HashData
{
public:
    T _data;
    HashData *_next;
    HashData(const T &data) : _data(data), _next(nullptr)
    {
    }
};
template <class T, class K, class KOrV, class ToIntFunc>
class HashTable;
template <class T,class KOrV,class ToIntFunc>
struct Iterator
{
    typedef Iterator self;
    typedef HashData<T> Data;

    T _data;
    std::vector<Data *> _table;
    Iterator(const T &data, const std::vector<Data *> &table) : _data(data), _table(table)
    {
    }
    self &operator++()
    {
        if (_data == nullptr)
        {
            return self(nullptr,_table);
        }
        Data *next = _data->next;
        if (next == nullptr)
        {
            int hashi = KOrV(ToIntFunc(_data)) % _table.size();
            while(table[++hashi])
            {
                return self(table[hashi],_table);
            }
            return self(nullptr,_table);
        }
        return self(next,_table);
    }
    self &operator--()
    {
        if(_data == nullptr)
    }
    bool operator!=(const self &it)
    {
        return it._data != _data;
    }
    T *operator->()
    {
    }
    T &operator*()
    {
    }
};
template <class T, class K, class KOrV, class ToIntFunc>
class HashTable
{
public:
    typedef HashData<T> Data;
    typedef Iterator<T,KOrV,ToIntFunc> iterator;

private:
    std::vector<Data *> _table;
    int _size = 0;
    int _capacity;
    ToIntFunc TtoI;

public:
    HashTable(size_t capacity = 1)
    {
        _capacity = capacity;
        _table.resize(_capacity);
    }
    ~HashTable()
    {
        for (auto it : _table)
        {
            Data *node = it;
            Data *next = nullptr;
            while (node)
            {
                next = node->_next;
                delete node;
                node = next;
            }
        }
    }
    iterator begin()
    {
        for (Data *it : _table)
        {
            if (it)
            {
                return iterator(it->_data, _table);
            }
        }
        return iterator(nullptr, _table);
    }
    iterator end()
    {
        return iterator(nullptr, _table);
    }
    bool insert(const T &data)
    {
        KOrV korv;
        if (find(korv(data)) == true)
        {
            return false;
        }
        if (_size >= _capacity)
        {
            std::cout << "扩容" << std::endl;
            std::vector<Data *> table;
            table.resize(_capacity * 2);
            table.swap(_table);
            _capacity *= 2;
            _size = 0;
            for (auto it : table)
            {
                Data *tmp = it;
                while (tmp)
                {
                    this->insert(tmp->_data);
                    tmp = tmp->_next;
                }
            }
        }
        int hashi = TtoI(korv(data)) % _table.size();
        // 找到对应的哈希位置
        if (_table[hashi] == nullptr)
        {
            _table[hashi] = new Data(data);
            ++_size;
            return true;
        }
        Data *record = nullptr;
        Data *nowNode = _table[hashi];
        while (nowNode)
        {
            record = nowNode;
            nowNode = nowNode->_next;
        }
        record->_next = new Data(data);
        ++_size;
        return true;
    }
    bool erase(const K &data)
    {
        if (find(data) == false)
        {
            return false;
        }
        KOrV korv;
        // 找到对应的哈希位置
        int hashi = TtoI(data) % _table.size();
        Data *record = nullptr;
        Data *nowNode = _table[hashi];
        while (nowNode)
        {
            if (korv(nowNode->_data) == data)
            {
                if (nowNode == _table[hashi])
                {
                    _table[hashi] = nowNode->_next;
                    delete nowNode;
                    nowNode = nullptr;
                    --_size;
                    return true;
                }
                record->_next = nowNode->_next;
                delete nowNode;
                nowNode = nullptr;
                --_size;
                return true;
            }
            record = nowNode;
            nowNode = nowNode->_next;
        }
        std::cerr << "erase error" << std::endl;
        exit(-1);
    }
    bool find(const K &data)
    {
        KOrV korv;
        int hashi = TtoI(data) % _table.size();
        Data *node = _table[hashi];
        if (node == nullptr)
        {
            return false;
        }
        while (node)
        {
            if (korv(node->_data) == data)
            {
                return true;
            }
            node = node->_next;
        }
        return false;
    }
};
